package code;

import java.util.Stack;


public class BSTiterator {
	
	public static class TreeNode {
	      int val;
	      TreeNode left;
	      TreeNode right;
	      TreeNode(int x) { val = x; }
	}
	/*
	 * 用栈来模拟递归的过程	
	 */
	private Stack<TreeNode> stack;
	private TreeNode it;
	
 	public BSTiterator(TreeNode root) {
        it=root;
        stack=new Stack<>();
        while(it!=null){
        	stack.add(it);
        	if(it.left==null)	break;
        	it=it.left;
        }
    }

    /** @return whether we have a next smallest number */
    public boolean hasNext() {
    	if(it==null)	return false;
		return true;
        
    }

    /** @return the next smallest number */
    public int next() {
    	if(it==null || stack.empty()) return 0;
    	int x=it.val;
    	moveNext();
    	return x;
    }
    
    public void moveNext(){
    	if(stack.empty())	return;
    	
    	stack.pop();
    	//将it的右子树的作为根节点压入栈中,此时it不能再次压入栈了，要不然是死循环
    	if(it.right==null){
    		//返回到自己的父节点，在栈顶
    		//如果栈为空，则整个树遍历完了
    		if(stack.empty())	it=null;
    		//it变成其父节点，且此时父节点的val最小，不能将右子树压入栈
    		else
    			it=stack.peek();
    		//不管如何，此次移动都需要结束
    		return;
    	}
    	//it的右子树存在，将自己pop出去之后，再将右子树的最小元素链压入栈中
    	else it=it.right;
    	while(it!=null){
    		stack.push(it);
    		if(it.left==null)	break;
    		it=it.left;
    	}
    }
    public static void main(String[] args){
    	TreeNode root=new TreeNode(5);
    	TreeNode node3=new TreeNode(3);
    	TreeNode node4=new TreeNode(4);
    	TreeNode node7=new TreeNode(7);
    	TreeNode node6=new TreeNode(6);
    	TreeNode node8=new TreeNode(8);
    	TreeNode node1=new TreeNode(1);
    	TreeNode node2=new TreeNode(2);
    	
    	root.left=node3;
    	root.right=node7;
    	
    	node3.left=node1;
    	node3.right=node4;
    	
    	node7.left=node6;
    	node7.right=node8;
    	
    	BSTiterator btsi=new BSTiterator(root);
    	while(btsi.hasNext()){
    		int x=btsi.next();
    		if(x==0)	break;
    		System.out.println(x);
    	}
    }
}
